from typing import List


class Solution:
    def __init__(self):
        self.temp = {}

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 这里可以对 wordDict 做一遍过滤
        return self.wordBreakI(0, s, wordDict)

    def wordBreakI(self, i, s: str, wordDict: List[str]):
        if i == len(s):
            return True
        for word in wordDict:
            wlen = len(word)
            if i + wlen > len(s):
                continue
            if s[i: i + wlen] == word:
                if i + wlen not in self.temp:
                    self.temp[i + wlen] = self.wordBreakI(i + wlen, s, wordDict)
                if self.temp[i + wlen]:
                    return True
        return False


# print(Solution().wordBreak("leetcode", ["leet", "code"]))
print(Solution().wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", [
      "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]))
# print(Solution().wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", [
    #   "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "ba"]))
# print(Solution().wordBreak("abcd", ["a","abc","b","cd"]))